package 二叉树相关问题;

public class 填充二叉树右侧节点 {
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

    public Node connect(Node root) {
        if (root==null)
            return root;
        connectTwoNode(root.left,root.right);
        return root;
    }

    private void connectTwoNode(Node left, Node right) {
        if (left==null || right==null)
            return;
        left.next=right;
        //连接相同父节点
        connectTwoNode(left.left,left.right);
        connectTwoNode(right.left,right.right);
        //连接不同父节点
        connectTwoNode(left.right,right.left);
    }
}
